package me.mingshan.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * https://leetcode.cn/problems/top-k-frequent-elements/description/
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 *
 * @author hanjuntao
 * @date 2025/7/2 0002
 */
public class L_347_top_k_frequent_elements {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(topKFrequent2(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }

    /**
     * 暴力解法
     *
     * 1. 创建一个 map，记录每个数字出现的次数
     * 2. 对map的键值对进行排序，排序规则为：按照 value 降序排序
     * 3. 创建一个结果数组，长度为 k
     * 4. 遍历 键值对list，把出现频率前 k 高的元素加入结果数组
     *
     * @param nums
     * @param k
     * @return
     */

    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int[] res = new int[k];
        List<Map.Entry<Integer, Integer>> collect = map.entrySet().stream()
                .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed())
                .collect(Collectors.toList());

        for (int i = 0; i < k; i++) {
            res[i] = collect.get(i).getKey();
        }
        return res;
    }

    /**
     * 桶排序
     *
     * 1. 创建一个 map，记录每个数字出现的次数
     * 2. 创建一个桶，索引为出现频率，集合内部为出现的数字
     * 3. 倒序遍历桶，把出现次数前 k 大的元素加入答案
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 桶排序
        // 索引为 出现频率
        // 集合内部为出现的数字
        int maxCnt = Collections.max(map.values());

        // 第二步：把出现次数相同的元素，放到同一个桶中
        List<Integer>[] buckets = new ArrayList[maxCnt + 1];
        Arrays.setAll(buckets, i -> new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            buckets[e.getValue()].add(e.getKey());
        }

        // 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        int[] ans = new int[k];
        int j = 0;
        for (int i = maxCnt; i >= 0 && j < k; i--) {
            for (int x : buckets[i]) {
                ans[j++] = x;
            }
        }
        return ans;
    }
}
